1380G - Circular Dungeon - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef pair<pi, ll> pii;
typedef set<ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i, s, e) for (int i = s; i <= int(e); ++i)
#define DEC(i, s, e) for (int i = s; i >= int(e); --i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i, x) for (auto i : x)
#define mem(x, i) memset(x, i, sizeof x)
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define maxn 500010
#define INF (ll)1e9
#define MOD 998244353
typedef pair<vi, int> pvi;
typedef pair<int, pi> ipi;
typedef vector<pii> vpii;
#define DEBUG 0
typedef pair <pi,pi> pipi;
typedef vector <pipi> vpipi;
typedef pair <string, int> psi;


int N,A[maxn],ss[maxn];
int qexp(int a,int b){
	int ans = 1;
	while (b){
		if (b&1) (ans *= a) %= MOD;
		(a *= a) %= MOD;
		b >>= 1;
	}
	return ans;
}
void solve(){
	cin >> N;
	FOR(i,1,N) cin >> A[i];
	sort(A+1,A+N+1,greater <int> ());
	FOR(i,1,N) ss[i] = (ss[i-1] + A[i])%MOD;
	
	int invN = qexp(N,MOD-2);
	FOR(k,1,N){
		int res = 0;
		for (int i=1,j=0;i<=N; i+=k,j++){
			(res += (j*(ss[min(N,i+k-1)] - ss[i-1]))%MOD)%=MOD;
		}
		res = (res + MOD) % MOD;
		cout << (res*invN)%MOD << ' ';
	}
}

int32_t main() {
	fast;
	
	solve();
	//~ cin >> TC;
	//~ while (TC--) solve();
	
}